package LeetCode.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 四数之和
 *
 * 固定其中一个数nums[i]，从余下数组中找三数之和为target-nums[i]
 * @author: leiwenkang02@meituan.com
 * @date: 2018/9/21
 * @time: 11:42
 */
public class Test18四数之和 {
    public static void main(String[] args) {
        int[] nums = {1, 0, -1, 0, -2, 2};
        List<List<Integer>> result = fourSum(nums, 0);
        for (int i = 0; i < result.size(); i++) {
            for (Integer num : result.get(i)) {
                System.out.print(num);
                System.out.print(" ");
            }
            System.out.println();
        }
    }
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length < 4) {
            return result;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 3; i++) {
            if (i == 0 || i > 0 && nums[i] != nums[i - 1]) {
                List<List<Integer>> threeSumResult = threeSum(nums, i + 1, nums.length - 1, target - nums[i]);
                if (threeSumResult.size() != 0) {
                    for (int j = 0; j < threeSumResult.size(); j++) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.addAll(threeSumResult.get(j));
                        result.add(list);
                    }
                }
            }
        }
        return result;

    }

    public static List<List<Integer>> threeSum(int[] nums, int start, int end, int target) {
        List<List<Integer>> result = new ArrayList<>();
        for (int i = start; i <= end - 2; i++) {
            if (i == start || i > start && nums[i] != nums[i - 1]) {
                int low = i + 1;
                int high = end;
                int sum = target - nums[i];
                while (low < high) {
                    if (nums[low] + nums[high] == sum) {
                        result.add(Arrays.asList(nums[i], nums[low], nums[high]));
                        while (low < high && nums[low] == nums[low + 1]) {
                            low++;
                        }

                        while (low < high && nums[high] == nums[high - 1]) {
                            high--;
                        }
                        low++;
                        high--;
                    } else if (nums[low] + nums[high] < sum) {
                        low++;
                    } else {
                        high--;
                    }
                }
            }
        }
        return result;
    }


}
